package com.binaryTree;

import java.util.Stack;

public class PathSum0303_112 {
    //递归
    public boolean hasPathSum0(TreeNode root, int targetSum) {
        if(root == null) return false;
        targetSum -= root.val;

        //叶子节点
        if(root.left == null && root.right == null) return targetSum==0;

        if(root.left != null){
            boolean left = hasPathSum(root.left, targetSum);
            if(left) return true;
        }

        if(root.right != null) {
            boolean right = hasPathSum(root.right, targetSum);
            if(right) return true;
        }

        return false;
    }

    //迭代
    //层序遍历
    public boolean hasPathSum1(TreeNode root, int targetSum) {
        if(root == null) return false;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        stack1.push(root);
        stack2.push(root.val);

        while (!stack1.isEmpty()){
            int len = stack1.size();

            while (len >0){
                TreeNode node = stack1.pop();
                Integer sum = stack2.pop();

                if(node.left == null && node.right == null && sum == targetSum) return true;

                if(node.left != null){
                    stack1.push(node.left);
                    stack2.push(sum + node.left.val);
                }

                if(node.right != null){
                    stack1.push(node.right);
                    stack2.push(sum + node.right.val);
                }
                len--;
            }
        }
        return false;
    }

    //迭代
    //DFS
    public boolean hasPathSum(TreeNode root, int targetSum) {
        Stack<TreeNode> sta1 = new Stack<>();
        Stack<Integer> sta2 = new Stack<>();

        if(root == null) return false;
        sta1.push(root);
        sta2.push(root.val);

        while (!sta1.isEmpty()){
            TreeNode node = sta1.pop();
            int sum = sta2.pop();

            if(node != null) {
                sta1.push(node);
                sta1.push(null);
                sta2.push(sum);
                if(node.right != null){
                    sta1.push(node.right);
                    sta2.push(sum + node.right.val);
                }
                if(node.left != null){
                    sta1.push(node.left);
                    sta2.push(sum + node.left.val);
                }
            }else {
                TreeNode temp = sta1.pop();
                if (temp.left == null && temp.right == null && sum == targetSum) return true;
            }
        }
        return false;
    }

}
